package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-03-04 19:16
 */
public class n_M_343 {
    public static void main(String[] args) {
        n_M_343 n = new n_M_343();
        int res = n.integerBreak(28);
        System.out.println(res);
    }

    /**
     * 贪心：
     * 数学思想：尽量拆分为2和3
     * https://leetcode-cn.com/problems/integer-break/solution/343-zheng-shu-chai-fen-tan-xin-by-jyd/
     *
     * @param n
     * @return
     */
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int a = n / 3;
        int b = n % 3;
        if (b == 0) {
            return (int) (Math.pow(3, a));
        }
        if (b == 1) {
            return (int) (Math.pow(3, a - 1) * 4);
        }
        return (int) (Math.pow(3, a) * 2);
    }

    /**
     * 动态规划
     * dp[]数组存放数字为i时，对i进行整数拆分得到的最大值
     * @param n
     * @return
     */
    public int integerBreak2(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int max=0;
            for (int j = 1; j < i; j++) {
                int cur=Math.max(j*(i-j),j*dp[i-j]);
                if (cur>max){
                    max=cur;
                }
            }
            dp[i]=max;

        }
        return dp[n];
    }
}
